We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order.

The paper proposes a family of kernels for graphs with ordered neighbourhoods and discrete labels. Any member of the family is obtained by generating a string-based representation of each node of a graph and a subsequent exploitation of the basic spectrum string kernel by Leslie et al. Specifically, the string associated to a node of the graph is efficiently and recursively generated via a tree traversal method that uses the neighbour ordering. The visit starts from a node and ends when the depth of the tree is h. Thus the visited subtrees are the starting features exploited by the kernel.

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.